package 二叉树的深度;

import java.util.LinkedList;

//题目描述
//输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
public class Solution
{
    public int TreeDepth(TreeNode root)
    {
        //一个节点的二叉树的深度是1
        if(root==null){
            return 0;
        }
        int left=TreeDepth(root.left);
        int right=TreeDepth(root.right);
        return Math.max(left,right)+1;
    }
    public int TreeDepth1(TreeNode root)
    {
        //判断输入
        if (root==null)
            return 0;
        //队列的方法
        LinkedList<TreeNode> treeNodes=new LinkedList<TreeNode>();
        treeNodes.offer(root);
        int depth=0;
        int size=0;
        //确保这一层的节点都遍历完之后，深度才加一
        while (!treeNodes.isEmpty())
        {
            size=treeNodes.size();
            while (size!=0)
            {
                TreeNode node = treeNodes.poll();
                if (node.left != null)
                    treeNodes.offer(node.left);
                if (node.right != null)
                    treeNodes.offer(node.right);

                size--;//当size=0时，本层节点遍历完成
            }
            depth++;
        }
        return depth;
    }

}
